Internet Info 1994 March/Internet Info CD-ROM (Walnut Creek) (March 1994).iso/inet/ien/ien-173

Text File | 1988-12-01 | 21KB | 438 lines

IEN 173


            Time Synchronization in DCNET Hosts
              D.L. Mills, COMSAT Laboratories
                         25-Feb-81


Introduction

The difficulty in establishing an  absolute  time  reference
for  use  in  internet measurements and experiments has been
often lamented.  While  time  standards  calibrated  to  the
precision  necessary for internet delay measurements (in the
order of a millisecond) are readily available, the  cost  to
equip  each  host which may participate in these experiments
is significant and the broadcast services they  depend  upon
may  not  be available where needed.  This note describes an
alternative   mechanism   using   local-net   protocols   to
synchronize  a  logical  clock  in each of a set of internet
hosts to a single physical  clock,  such  as  an  NBS  radio
clock.   The  mechanism has been incorporated as an integral
component of the DCNET network routing algorithm and depends
for  its  accuracy  upon the careful control of link delays.
For this reason it may not be practically  applicable  as  a
retrofit  in  the  ARPANET,  for example.  Nevertheless, the
principles can be  applied  in  cases  where  somewhat  less
precision is acceptable and where the participating hosts or
gateways support the required protocol.

The DCNET Routing Algorithm

The  DCNET  includes  a  number  of  PDP11-compatible  hosts
interconnected  by  dedicated  and  dial-up links of various
types,  including  simple   synchronous   and   asynchronous
point-to-point links, high-speed interprocessor channels and
self-contained retransmission systems.  All of  these  links
include  inherent  delays which vary with transmission rate,
message  length  and   coding,   as   well   as   occasional
retransmissions.  In addition, the host operating system can
introduce delays  due  to  interrupt  latency,  interprocess
communication   and   process   scheduling.    These  delays
typically include  a  fixed  component  due  to  propagation
phenomena,   together   with  a  relatively  small  variable
component   due   to   internal   queueing,    coding    and
retransmission mechanisms.

The  DCNET  architectural  design  includes  the  notion  of
virtual host, which is a process resident in a physical host
and labelled with a unique internet address.  One or more of
these virtual hosts can reside in a single physical host and
can migrate about the network from time to time in arbitrary
ways.   Each  virtual  host  can  support  multiple internet
protocols, connections and, in addition,  a  virtual  clock.
Each  physical  host  contains  a  physical  clock which can
operate at an arbitrary rate  and,  in  addition,  a  32-bit

Time Synchronization in DCNET Hosts                 PAGE   2



logical  clock  which operates at 1000 Hz.  Not all physical
hosts implement the full 32-bit precision; however, in  such
cases  the  resolution  of the logical clock may be somewhat
less.

Routing of datagrams from a physical host  to  each  of  the
virtual  hosts in the network is determined by a set of Host
Tables, one in each physical  host,  which  are  updated  by
HELLO  messages  exhanged on the links connecting them.  The
HELLO messages are exchanged frequently, but not  so  as  to
materially  degrade  the throughput of the link for ordinary
data  messages.   They  contain  information  necessary   to
compute  the roundtrip delay and logical clock offset of the
receiving  physical  host  relative  to  the  sending   one,
together with a table of delay and offset estimates computed
between the sending physical host and each  of  the  virtual
hosts  in  the  network.  For the purpose of these estimates
the delay and offset of each virtual host  relative  to  the
physical host in which it resides is assumed zero.

The Host Table  is  updated  by  HELLO  messages  from  each
neighboring  physical  host and in certain other cases.  The
updating algorithm is similar to that used  in  the  ARPANET
and other places in that the roundtrip delay calculated to a
neighbor is added to each of the delay  estimates  given  in
its  HELLO message and compared with the corresponding delay
estimates in the Host Table.  If a delay  computed  in  this
way  is  less  than the delay already in the Host Table, the
routing  to  the  corresponding  virtual  host  is   changed
accordingly.   The  detailed  operation  of  this algorithm,
which includes provisions for host up-down  logic  and  loop
suppression, is summarized elsewhere [1].

Virtual Clocks

The Host Table  update  procedure  represents  a  convenient
mechanism  to  implement  a  common  time reference for each
logical clock in the network.  For this purpose each virtual
clock  residing  in  a  physical  host  is assumed to run in
synchronism with zero offset relative to the  logical  clock
of that host.  The offsets of the other virtual hosts in the
network, relative to this logical clock, are computed  along
with  the  delays  as HELLO messages arrive from neighboring
physical hosts.  A physical host,  upon  receiving  a  HELLO
message,  adds  one-half  the difference between its logical
clock and its neighbor's  logical  clock  contained  in  the
HELLO  message  to  each of the offset values in the message
and stores the result in its own Host Table.  Note that both
the  delay and offset values are stored only if the neighbor
is in fact on the least-delay path to the virtual  host  and
that  the  link  delay  is assumed equal in both directions.
Also, note that should a virtual host move from one physical
host  to  another, the delays and offsets in all Host Tables

Time Synchronization in DCNET Hosts                 PAGE   3



relative to that virtual host would likely change.

Any user process  in  a  physical  host  can  reference  its
time-of-day  calculations to any virtual host in the network
by simply adding the appropriate virtual clock offset to the
current value of the logical clock.  Ordinarily, all network
experiments use the same  virtual  host  for  this  purpose,
although   not   necessarily  the  same  one  in  successive
experiments.  In  the  current  implementation  one  of  the
physical  hosts contains a special virtual host connected to
an NBS radio clock.  The offset stored  in  the  Host  Table
corresponding  to  this  virtual host reflects the offset of
this clock relative to the logical clock.  Using  the  above
mechanism,  the remaining physical hosts can reference their
logical clocks to the receiver as well.  One of the physical
hosts  is  shortly  to be moved not far from an atomic clock
which is referenced to the Naval Observatory clock  using  a
local  television  station.  We are now assembling interface
hardware for access to this standard and  plan  to  use  the
above mechanism to reference all clocks to it.

Implementation Considerations

The absolute accuracy of the available NBS radio  clocks  is
claimed  to  be  of  the order of a millisecond.  Since this
precision  compares  with  that  of  the  standard  internet
timestamps  used for the most precise delay measurements, it
would be natural to strive  for  a  corresponding  precision
within  a  set of hosts using the mechanism described above.
Ordinarily, this would require a crystal oscillator, counter
and  interface at each host.  The oscillator stability found
in commercial equipment of this type is of the  order  of  a
few  parts  per  million  under  laboratory  conditions.  An
uncorrected logical clock based on this equipment  could  be
expected  to  maintain  time  to within a millisecond for at
least eight minutes and to within three minutes in a year.

In  the  case  of  the  mechanism   described   above,   the
corrections  take  the form of offsets contained in periodic
HELLO messages.  A careful analysis  of  the  non-systematic
errors inherent in these messages reveals contributions from
a number of sources dominated by the following:

1.  The interval between the instant the local clock is read
    and  the  departure of the first bit of the timestamp on
    the link.

2.  The  effect  of  the  data  coding   conventions   (e.g.
    character  stuffing  or  bit  stuffing) used to maintain
    data transparency.

3.  The effect of retransmissions, where used.

Time Synchronization in DCNET Hosts                 PAGE   4



4.  The interval between the arrival of the first bit of the
    timestamp  and the instant it is compared with the local
    clock.

The effects of the first and last of these delays  has  been
minimized  in the DCNET implementation by careful control of
internal latencies and scheduling mechanisms and is  limited
to the order of a millisecond.  The effects of character and
bit stuffing can be estimated under the assumption that  all
character  codes  are  equally  likely.   In  that case, the
effects of character stuffing would contribute a  factor  of
about  1/256 to the uncertainty in data rate and the effects
of bit stuffing would contribute about 1/32.  Thus, for  the
case  of  1200-bps  character-stuffing  links carrying HELLO
messages of typically 800 bits, the uncertainty would be  of
the  order of two milliseconds.  The effects of bit stuffing
in  the  high-speed  links  are  negligible  in  comparison.
Although  HELLO  messages are never retransmitted by a DCNET
host, some of the DCNET links, in particular those based  on
the   ACC   Error  Control  Units  (ECU),  contain  internal
retransmission features.   Since  retransmissions  occur  so
seldom in the present configuration, their effects have been
ignored; however, a simple range-gate technique  similar  to
that  used  in  radar  systems  could  be used to filter out
retransmissions, should that become a problem.

From the above  considerations  the  uncertainty  in  delays
measured  using HELLO messages can be conservatively assumed
in the order of five milliseconds.  For ease of analysis  in
the following, we will assume the uncertainty to be a random
variable  with  a  zero-mean  Gaussian  distribution  and  a
standard  deviation of five milliseconds.  Thus, in order to
reduce the  uncertainty  to  the  order  of  a  millisecond,
something  over  25  independent  samples would be required.
The maximum interval between successive  HELLO  messages  is
thirty  seconds,  so  that  the  required  precision  can in
principle be achieved in about twelve minutes.

Precise determination of clock  offsets  requires  that  the
drift  rates between the various logical clocks be estimable
with sufficient precision.  The approach chosen in the DCNET
design  has  been  to initialize a variable representing the
current offset of the local logical clock relative  to  that
of  a  neighbor  each time a HELLO message arrives from that
neighbor which updates the Host Table entry for the selected
virtual  host.   Once  each second the period of the logical
clock is increased by a quantity equal  to  1/1024  of  this
variable and the variable is decreased by the same quantity.
The effect is that of  a  first-order  recursive  filter  in
smoothing  the  corrections  and  distributing them so as to
minimize the phase jitter as viewed by the user process.  In
addition, if updates from the selected virtual host are lost
due to failure of some host or link, the logical clock  will

Time Synchronization in DCNET Hosts                 PAGE   5



continue  the  correction  process  until  the  last  offset
received is compensated.

In order to provide for the initial setting of  the  logical
clock  and  subsequent  drift  correction without disruptive
phase discontinuties, the full 32-bit clock value is  stored
only  if  the (signed) offset exceeds 16 bits; that is, only
if the high-order 16 bits must be changed.  In  other  cases
the  low-order 16 bits are corrected by slewing the phase of
the clock according  to  the  current  offset  as  described
above.    The  high-order  16  bits  correspond  roughly  to
minutes,  while  the  low-order  16   bits   correspond   to
milliseconds.   Most  internet measurments will be concerned
primarily with the latter, so this behavior is  appropriate.
This  yields a slew rate of about one microsecond per second
for each millisecond of offset.

The dynamics of this procedure insure a smooth transition in
apparent  drift rate from a maximum of 30 parts per thousand
for the maximum offset to  one  part  per  million  for  the
smallest.   The maximum time required to slew the phase of a
physical clock  over  the  full  (plus-minus)  thirty-second
range  to  steady  state  is  about  two  hours.  During the
slewing interval the offset estimates continue to be  valid,
although of somewhat degraded accuracy.

In  a  multiple-host   network   where   the   logical-clock
corrections  must  pass  through a number of physical hosts,
the robustness of this method depends on the cooperation  of
all  intervening hosts.  In general, this requires all hosts
to track the same virtual  host  offset  and,  in  addition,
introduces   additional  dynamics  in  the  drift-correction
process.  The effect is that of a set of coupled first-order
recursive   filters,  where  the  input  of  each  stage  is
connected to the output of the previous stage, and all  have
the same time constant described previously.  So long as the
drift rates are constant over at least several  hours,  this
is  not  a  problem; however, in the case where some logical
clocks are derived from power-line sources, this can lead to
significant loss in accuracy.

On Power Line Clocks

The short-term drift rates of power-line clocks relative  to
standard time have been observed to exceed several parts per
thousand, with sharp changes in sign and magnitude  occuring
near  periods  of  large  load fluctuations.  In experiments
with the  current  DCNET  implementation,  discrepancies  of
several   seconds   are   routinely   observed  between  the
power-line clock and the NBS radio clock.   However,  it  is
evident  that the power systems for considerable portions of
this country are closely synchronized in phase  relative  to
each  other.   For  instance,  the  DCNET  hosts  at  COMSAT

Time Synchronization in DCNET Hosts                 PAGE   6



Headquarters in Washington, D.C.,  and  at  Ford  Scientific
Research Laboratories in Dearborn, Michigan, have never been
observed to slip a power-line cycle relative to each other.

These observations suggest that, if logical clocks are to be
synchronized  to  an  atomic  clock or NBS radio clock, then
physical clocks based on the power mains are  not  feasible,
at  least  for  accuracies of the order of milliseconds.  On
the  other  hand,  for  the  short-term  delay  measurements
required  for  many internet experiments and where reference
to absolute time is not essential,  the  use  of  the  power
mains as a synchronization reference may be quite practical.
This holds, of course, only in those cases where  the  power
systems in the areas where measurements are made are in fact
synchronous and probably would not apply, for  example,  for
European sites.

On Radio Clocks

Two of the NBS  radio  clocks  on  the  market  include  the
Spectracom  8170  WWVB  Synchronized Clock and the True Time
468-DC Satellite Synchronized Clock.  The  former  uses  the
60-KHz  NBS  broadcast  from  Boulder,  Colorado,  while the
latter uses the NOAA GOES  satellites.   Both  have  claimed
accuracy  in  the  order of a millisecond and both support a
service area including the  continental  US.   A  Spectracom
8170  is  now in service connected to one of the DCNET hosts
and serves as a master clock for the network.  A  few  notes
on  its  characteristics  may  be of interest, especially to
others in the internet community planning on  using  similar
equipment.

The characteristics of electromagnetic wave  propagation  at
60   KHz  combine  some  features  of  the  waveguide  model
applicable at frequencies below about 30  KHz  and  the  ray
model  applicable  at  higher  frequencies [2].  Both models
explain how the E layer, an  ionized  region  about  100  km
above    the    earth's    surface,   guides   or   reflects
electromagnetic waves over long distances.  In the  case  of
60-KHz   transmissions  from  Boulder,  the  models  predict
greater signal attenuation at  times  of  the  most  intense
ionizing  radiation from the sun on the D region, which lies
just below the E region and through which the  signals  must
pass.   Thus,  one  would expect that received signal levels
would be highest  at  nighttime  in  winter  and  lowest  in
daytime  in summer, with respect to the midpoint of the path
from Boulder to the receiver.  This  has  been  observed  in
Washington,  DC, where the receiver often drops out of phase
lock  for   varying   periods   in   the   late   afternoon.
Measurements   of   the   received   signal   level  with  a
communications  reveiver   confirm   variations   of   20-30
decibels.

Time Synchronization in DCNET Hosts                 PAGE   7



Atmospheric discharges (called sferics) due to lightning can
be a severe problem at these frequencies in Summer and could
be expected to disrupt the receiver during  summer  evenings
when  propagation conditions are relatively good from active
electrical  areas  like  the  Gulf  Coast.   Although  other
stations  share the 60-KHz assigned frequency, including MSF
in Rugby, UK, co-channel interference does not seem to be  a
problem.   On  the  other  hand,  some  household electrical
appliances, including  television  deflection  circuits  and
solid-state  lamp  dimmers,  can  generate copious harmonics
that disrupt the receiver.   The  ferrite  antenna  supplied
with  the receiver does not seem to be as effective as would
ordinarily be expected in dealing with this problem.

Even when phase lock has  been  lost,  the  receiver  coasts
indefinately using the last clock update received.  Although
the receiver indicates a signal loss of  over  ten  minutes,
both by a front-panel indicator and in the time message sent
to the attached  host,  the  indicated  time  should  remain
accurate  to  within  an  order of one part in a million, as
suggested by tests using an accurate frequency counter.  The
DCNET implementation polls the receiver every thirty seconds
and tracks the time messages as long as they are  available,
but  retains the last received message for later inspection,
if desired.  In addition, if the time messages are lost  the
system  continues  to  follow  the  information  in the last
message.

Summary and Conclusions

The  above  analysis  indicates  that  logical   clocks   in
neighboring   physical   hosts  can  be  synchronized  using
ordinary local-network routing update messages, so  long  as
the  oscillator  drift  rates  are  stable and do not differ
radically.   A  multiple-host   network   can   readily   be
synchronized  so long as each pair of neighboring hosts can,
although this can require rather long settling times.  Here,
two  hosts are assumed synchronized when the offsets between
their respective logical  clocks  can  be  calculated  to  a
precision of the order of a millisecond.

Delay and offset variances along internet paths  are  likely
to  be  so  large  as  to make the technique described above
impractical, at least  if  millisecond  accuracy  is  to  be
preserved.   The  present plan of installing radio clocks in
the internet  gateways  appears  to  be  the  most  sensible
alternative.   The  gateways  thus  form  an attractive time
reference for the hosts on the attached local networks.  The
gateways  themselves could include the offsets between their
own clocks in Gateway-Gateway Protocol (GGP) routing  update
messages,  if  not  all of them were equipped with NBS radio
clocks, and could conveniently provide this  information  in
GGP  echo messages to the local network hosts.  In order for

Time Synchronization in DCNET Hosts                 PAGE   8



this to be most effective, the timestamping  mechanism  used
by the gateways (and hosts, of course) should be implemented
as close  to  the  network  interface  driver  as  possible,
preferably by the driver itself.

A local-network host can synchronize its logical clock to  a
gateway by a mechanism suggested by the DCNET routing update
procedure.  The host sends a  GGP  echo  packet  timestamped
with its logical clock to a gateway.  The gateway timestamps
it with its own logical clock upon arrival and again when it
is  retransmitted  to  the  host.  The local host uses these
three timestamps, together with the time of arrival  of  the
reply  packet,  to compute the delay and offset as described
above.  The use of three timestamps in the GGP  echo  packet
allows  the host to compensate for the internal delay within
the gateway, if significant.

References

1.  COMSAT Laboratories Quarterly  Progress  Reports.   Stay
    tuned.

2.  Davies,  K.    Ionospheric   Radio   Propagation.    NBS
    Monograph  80, National Bureau of Standards, Washington,
    DC, 1966.